package dp.leetcode_198_easy;

public class BestSolution {
    /**
     * @param nums 数组长度代表房间个数，数组元素代表房间里面的金额。
     * @return
     */
    //动态规划 + 无空间优化解法（ 时间复杂度O(N) 空间复杂度O(N) ）
    public int rob(int[] nums) {
        //base case
        if (nums == null || nums.length == 0) {
            return 0;
        }
        //房间个数 共有数组长度这么多个
        int houseCount = nums.length;
        //如果只有一个房间，直接返回
        if (houseCount == 1) {
            //数组下标从0开始，nums[0]代表第一间房
            return nums[0];
        }
        //定义动态规划表
        //一共n间房 (0 ~ n -1)
        int[] dp = new int[houseCount];
        //只有一间房
        dp[0] = nums[0];
        //两间房
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.max(
                    //不选i，则选前i - i间房的最大金额
                    dp[i - 1],
                    //选i， 则前i - 2间的最大金额 + i
                    nums[i] + dp[i - 2]
            );
        }
        return dp[houseCount - 1];
    }

    //最优解
    public int bestRob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int houseCount = nums.length;
        if (houseCount == 1) {
            return nums[0];
        }
        int[] dp = new int[houseCount];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        /*
            根据dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
            dp[i]的值只跟dp[i - 1] 和 dp[i -2]两个值有关
            使用两个变量记录这两个值
         */
        int pre = dp[0];
        int cur = dp[1];
        for (int i = 2; i < dp.length; i++) {
            //dp[2] = max(dp[1] , nums[1] + dp[0])
            //dp[3] = max(dp[2] , nums[2] + dp[1])
            //dp[4] = max(dp[3] , nums[3] + dp[2])
            int temp = cur;
            cur = Math.max(cur, nums[i] + pre);
            pre = temp;
        }
        return cur;
    }

    //最精简版本
    public int perfectRob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int twiceCur = 0;
        int OnceCur = 0;
        for (int i = 0; i < nums.length; i++) {
            int temp = OnceCur;
            OnceCur = Math.max(OnceCur, nums[i] + twiceCur);
            twiceCur = temp;
        }
        return OnceCur;
    }
}
